package org.slusk.thynwor.corestructures;

import java.awt.Color;
import java.awt.Component;
import java.awt.Image;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;

import javax.swing.ImageIcon;
import javax.swing.JLabel;
import javax.swing.JTable;
import javax.swing.table.AbstractTableModel;
import javax.swing.table.DefaultTableCellRenderer;
import javax.swing.table.TableCellRenderer;

import org.slusk.thynwor.corestructures.Region.RegionType;
import org.slusk.thynwor.util.Coordinates;
import org.slusk.thynwor.util.Direction;
import org.slusk.thynwor.util.ThynworException;

public class GridMap extends AbstractTableModel {
	
	private static final long serialVersionUID = -7320808953239720162L;
	
	private static final int[] neighborProviderRelativeCoords = {
			-1, -1,
			0, -1,
			1, -1,
			-1, 0, 
			1, 0,
			-1, 1,
			0, 1,
			1, 1
	};
	
	public static final Coordinates[] neighborRelativeCoords = {
		new Coordinates(0,-1)
		,new Coordinates(1,-1)
		,new Coordinates(1,0)
		,new Coordinates(1,1)
		,new Coordinates(0,1)
		,new Coordinates(-1,1)
		,new Coordinates(-1,0)
		,new Coordinates(-1,-1)
	};
	
	private GridCell cells[][];
	private int width;
	private int height;
	private double maxDistance;
	protected int specialManhattanMaxDistance;
	private LinkedList<Region> regionList;
	
	private CustomTableCellRenderer cellRenderer;
	
	static {
		
	}
	
	public GridMap(int width, int height) {
		this.height = height;
		this.width 	= width;
		cells = new GridCell[height][width];
		
		maxDistance = Math.sqrt(
				Math.pow(width - 1, 2) 
				+ Math.pow(height - 1, 2)
		);
		
		specialManhattanMaxDistance = width > height ? width - 1 : height - 1;
		
		regionList = new LinkedList<Region>();
		initializeCells();
		createTableCellRenderer();
	}
	
	private void initializeCells() {
		for (int y = 0; y < height; y++) {
			for (int x = 0; x < width; x++) {
				cells[y][x] = new GridCell(null);
			}
		}
	}
	
	protected double normalizeDistance(double distance) {return distance / maxDistance;}
	protected double normalizeSpecialManhattanDistance(double distance) {return distance / specialManhattanMaxDistance;}
	
	public void removeEntity(Entity e) {
		// Break the link
		GridCell gc = get(e.getCoordinates());
		gc.setContents(null);
	}

	public boolean isFree(Coordinates coords) {
		if (isInBounds(coords) && null == cells[coords.y][coords.x].getContents())
			return true;
		return false;
	}
	
	public boolean isFree(int x, int y) {
		if (isInBounds(x, y) && null == cells[y][x].getContents())
			return true;
		return false;
	}

	public boolean isInBounds(Coordinates coords) {
		if (coords.x >= 0 && coords.x < width && coords.y >=0 && coords.y < height) return true;
		return false;
	}

	public boolean isInBounds(int x, int y) {
		if (x >= 0 && x < width && y >=0 && y < height) return true;
		return false;
	}

	public GridCell get(Coordinates coords) {
		return cells[coords.y][coords.x];
	}
	public GridCell get(int x, int y) {
		return cells[y][x];
	}

	public void moveEntityTo(Entity entity, Coordinates coords) throws ThynworException {
		if (!isFree(coords)) {
			throw new ThynworException("GRIDMAP: entity sought coordinates " + coords.x + ", " + coords.y + " but that GridCell is not available.");
		}
		GridCell gc = get(entity.getCoordinates());
		gc.setContents(null);
		gc = get(coords);
		gc.setContents(entity);
	}
	
	public String getDisplayString() {
		StringBuilder s = new StringBuilder();
		
		s.append("+");
		for (int x = 0; x < width; x++) s.append("-");
		s.append("+\n");
		for (int y = 0; y < height; y++) {
			s.append("|");
			for (int x = 0; x < width; x++) {
				s.append((null != cells[y][x].getContents() ? cells[y][x].getContents().getDisplayCharacter() : " " ));
			}
			s.append("|\n");
		}
		s.append("+");
		for (int x = 0; x < width; x++) s.append("-");
		s.append("+\n");
		return s.toString();
	}

	public ArrayList<Direction> findAvailableDirectionsForCoordinates(Coordinates coords) {
		ArrayList<Direction> list = new ArrayList<Direction>();
		for (Direction direction : Direction.values()) {
			if (isFree(directionToCoordinates(direction, coords))) list.add(direction);
		}
		return list;
	}
	
	public ArrayList<Entity> buildListOfAdjacentEntities(Coordinates c) {
		ArrayList<Entity> list = new ArrayList<Entity>();
		Coordinates adjacent;
		Entity entity;
		for (Direction direction : Direction.values()) {
			adjacent = directionToCoordinates(direction, c);
			if (isInBounds(adjacent)) {
				entity = get(adjacent).getContents();
				if (null != entity) list.add(entity);
			}
		}
		return list;
	}
	
	
	public ArrayList<Entity> buildListOfAdjacentNonBotEntities(Coordinates c) {
		ArrayList<Entity> list = new ArrayList<Entity>();
		Coordinates adjacent;
		Entity entity;
		for (Direction direction : Direction.values()) {
			adjacent = directionToCoordinates(direction, c);
			if (isInBounds(adjacent)) {
				entity = get(adjacent).getContents();
				if (null != entity && !(entity instanceof Bot)) list.add(entity);
			}
		}
		return list;
	}
	
	
	public ArrayList<Entity> buildListOfSpecificAdjacentEntities(Coordinates c, Class<?> clazz) {
		ArrayList<Entity> list = new ArrayList<Entity>();
		Coordinates adjacent;
		Entity entity;
		for (Direction direction : Direction.values()) {
			adjacent = directionToCoordinates(direction, c);
			if (isInBounds(adjacent)) {
				entity = get(adjacent).getContents();
				if (null != entity && entity.getClass().equals(clazz) ) list.add(entity);
			}
		}
		return list;
	}
	
	/**
	 * Retrieve a list of entities that appear on the map within a specified rectangle.
	 * @param topLeft The top left coordinates of the rectangle, inclusive.
	 * @param bottomRight The bottom right coordinate of the rectangle, inclusive.
	 * @param clazz The class (entity type) you are looking for.
	 * @return
	 */
	public ArrayList<Entity> getListOfEntitiesInRange(Coordinates topLeft, Coordinates bottomRight, Class<?> clazz) {
		Entity e = null;
		ArrayList<Entity> list = new ArrayList<Entity>();
		for (int y = topLeft.y; y <= bottomRight.y; y++) {
			for (int x = topLeft.x; x <= bottomRight.x; x++) {
				e = get(x, y).getContents();
				if (null != e && e.getClass().equals(clazz)) {
					list.add(e);
				}
			}
		}
		
		return list;
	}
	
	public Coordinates generateRandomFreeCoordinates() {
		Coordinates c;
		
		do {
			c = generateRandomCoordinates();
		} while (!isFree(c));
		return c;
	}
	
	public Coordinates generateRandomFreeCoordinatesNotInRegion(RegionType type) {
		Coordinates c;
		do {
			c = generateRandomCoordinates();
		} while (!isFree(c) || getSpecificRegionsAt(c, type).size() != 0);
		return c;
	}
	
	public Coordinates generateRandomFreeCoordinatesInRegion(Region region) {
		Coordinates c;
		do {
			c = generateRandomCoordinatesInRange(region.topLeft, region.bottomRight);
		} while (!isFree(c));
		return c;
	}

	public Coordinates generateRandomCoordinates() {
		int x = (int) (Math.random() * width);
		int y = (int) (Math.random() * height);
		return new Coordinates(x, y);
	}
	
	public Coordinates generateRandomCoordinatesInRange(Coordinates topLeft, Coordinates bottomRight) {
		int x = (int) (Math.random() * (bottomRight.x - topLeft.x + 1)) + topLeft.x;
		int y = (int) (Math.random() * (bottomRight.y - topLeft.y + 1)) + topLeft.y;
		return new Coordinates(x, y);
	}
	
	public static Coordinates directionToCoordinates(Direction direction, Coordinates currentCoords) {
		int x = currentCoords.x;
		int y = currentCoords.y;
		switch (direction) {
		case N:
			y -= 1;
			break;
		case NE:
			y -= 1;
			x += 1;
			break;
		case E:
			x += 1;
			break;
		case SE:
			y += 1;
			x += 1;
			break;
		case S:
			y += 1;
			break;
		case SW:
			y += 1;
			x -= 1;
			break;
		case W:
			x -= 1;
			break;
		case NW:
			y -= 1;
			x -= 1;
			break;
		}
		return new Coordinates(x, y);
	}
	
	public static double calculateDistance(Coordinates c1, Coordinates c2) {
		return Math.sqrt( Math.pow(c1.x-c2.x, 2) + Math.pow(c1.y-c2.y, 2));
	}
	
	public static double calculateManhattanDistance(Coordinates c1, Coordinates c2) {
		return Math.abs(c1.x-c2.x) + Math.abs(c1.y-c2.y);
	}
	
	/**
	 * Special Manhattan distance: the manhattan distance if you are
	 * allowed to move diagonally.
	 * @param c1 First set of coordinates.
	 * @param c2 Second set of coordinates.
	 * @return The Special Manhattan distance between the two sets of coordinates.
	 */
	public static int calculateSpecialManhattanDistance(Coordinates c1,
			Coordinates c2) {
		int xdist = Math.abs(c1.x-c2.x);
		int ydist = Math.abs(c1.y-c2.y);
		return xdist > ydist ? xdist : ydist;
	}
	
	
	/**
	 * Returns directions adjacent to and including the direction argument.
	 * I.e., if you supply north, you get NW, N, NE. 
	 * @param direction The direction.
	 * @return A list of adjacent directions including the direction provided.
	 */
	public static LinkedList<Direction> getSimilarDirections(Direction direction) {
		LinkedList<Direction> list = new LinkedList<Direction>();
		list.add(direction);
		list.add(Direction.values()[(direction.ordinal()+1)%8]);
		list.add(Direction.values()[(direction.ordinal()+7)%8]);
		return list;
	}

	/**
	 * Returns directions adjacent to and including the direction argument that are free.
	 * I.e., if you supply north, you get NW, N, NE. 
	 * @param direction The direction.
	 * @return A list of adjacent directions including the direction provided.
	 */
	public LinkedList<Direction> getSimilarAvailableDirections(Coordinates coords, Direction direction) {
		LinkedList<Direction> list = getSimilarDirections(direction);
		LinkedList<Direction> ilist = (LinkedList<Direction>) list.clone();
		
		Coordinates c;
		
		for (Direction d : list) {
			c = directionToCoordinates(d, coords);
			if (!isFree(c)) ilist.remove(d);
		}
		return ilist;				
	}
	
	public LinkedList<Direction> getAvailableDirections(Coordinates coords) {
		LinkedList<Direction> list = new LinkedList<Direction>();
		for (Direction d : Direction.values()) {
			if (isFree(GridMap.directionToCoordinates(d, coords))) list.add(d);
		}
		
		return list;
	}
	
	public int getColumnCount() {
		return width;
	}
	public int getRowCount() {
		return height;
	}

	public Object getValueAt(int arg0, int arg1) {
		return null != cells[arg0][arg1].getContents() ? cells[arg0][arg1].getContents().getDisplayCharacter() : ' ';
	}

	public boolean isCellEditable(int arg0, int arg1) {
		// TODO Auto-generated method stub
		return false;
	}

	public ArrayList<Coordinates> findAdjacentFreeCoordinates(Coordinates coords) {
		ArrayList<Coordinates> list = new ArrayList<Coordinates>();
		for (Direction direction : Direction.values()) {
			if (isFree(directionToCoordinates(direction, coords))) list.add(directionToCoordinates(direction, coords));
		}
		return list;
	}

	public static Direction coordinatesToDirection(Coordinates srcCoords, Coordinates tgtCoords) {
		Direction d = null;

		double dx = srcCoords.x - tgtCoords.x;
		double dy = srcCoords.y - tgtCoords.y;
		double bearing = Math.toDegrees(Math.atan2(dy, dx)) + 360;
		double boc = bearing / 360 * 8;
		int dir = ((int)boc + 6) % 8;
		
		return Direction.values()[dir];
	}

	public void createTableCellRenderer() {
		this.cellRenderer = new CustomTableCellRenderer();
	}
	
	class CustomTableCellRenderer extends DefaultTableCellRenderer {

		public Component getTableCellRendererComponent(JTable table,
				Object value, boolean isSelected, boolean hasFocus, int rowIndex, int colIndex) {
			Component cell = super.getTableCellRendererComponent(table, value, isSelected, hasFocus, rowIndex, colIndex);
			((JLabel)cell).setOpaque(true);
			Entity e = get(colIndex, rowIndex).getContents();
			if (e == null) {
				((JLabel)cell).setText(value.toString());
				cell.setBackground(new Color(0, 0, 0));
				((JLabel)cell).setIcon(null);
				// Check if the coordinates are in a Region; if so, let the region render the cell.
				for (Region region : regionList) {
					if (region.contains(colIndex, rowIndex)) {
						region.render(cell);
						break;	// Just do the first one.
					}
				}

			} else {
				e.render(cell);
			}
				
			return cell;
		}	
	}
	

	public TableCellRenderer getCellRenderer() {
		return cellRenderer;
	}
	
	protected ArrayList<Coordinates> getFreeBorderSpaces() {
		ArrayList<Coordinates> list = new ArrayList<Coordinates>();
		int x = 0, y = 0;
		
		for (; x < width; x++) {
			if (isFree(x, y)) {
				list.add(new Coordinates(x, y));
			}
		}
		
		x = 0;
		for (y = 1; y < height; y++) {
			if (isFree(x, y)) {
				list.add(new Coordinates(x, y));
			}
		}
		
		x = width - 1;
		for (y = 1; y < height; y++) {
			if (isFree(x, y)) {
				list.add(new Coordinates(x, y));
			}
		}
		
		y = height - 1;
		for (x = 1; x < width - 1; x++) {
			if (isFree(x, y)) {
				list.add(new Coordinates(x, y));
			}
		}
		
		return list;
	}
	
	/**
	 * Adds a region to this map.
	 * @param topLeft		Top-left corner of the region.
	 * @param bottomRight	Bottom-right corner of the region.
	 * @param type			The type of region.
	 * @throws ThynworException Throws exception if any of the coordinates are out of bounds.
	 */
	public void createRegion(Coordinates topLeft, Coordinates bottomRight, RegionType type) throws ThynworException {
		if (isInBounds(topLeft) && isInBounds(bottomRight)) {
			regionList.add(new Region(topLeft, bottomRight, type));
		}
		else {
			throw new ThynworException("Unable to create region: coordinates out of bounds: " + topLeft + " - " + bottomRight);
		}
	}
	
	/**
	 * Removes the specified region from the map.
	 * @param region The region to remove.
	 * @return Returns true if any region was removed.
	 */
	public boolean removeRegion(Region region) {
		return regionList.remove(region);
	}
	
	/**
	 * Removes all occurences of a given type of region.  
	 * @param type The type of region to remove.
	 * @return Returns true if any region was removed.
	 */
	public boolean removeRegionType(RegionType type) {
		LinkedList<Region> regionsForRemoval = new LinkedList<Region>();
		boolean happened = false;
		for (Region region : regionList) {
			if (region.type == type) {
				regionsForRemoval.add(region);
			}
		}
		for (Region region : regionsForRemoval) {
			if (regionList.remove(region)) happened = true;
		}
		
		return happened;
	}
	
	/**
	 * Clears all regions from this map.
	 */
	public void clearAllRegions() {
		regionList.clear();
	}
	public LinkedList<Region> getRegions() {return regionList;}
	
	public LinkedList<Region> getRegionsOfType(RegionType type) {
		LinkedList<Region> list = new LinkedList<Region>();
		for (Region region : regionList) {
			if (region.type == type) list.add(region);			
		}
		return list;
	}
	
	public Region getClosestRegionOfType(Coordinates coords, RegionType type) {
		double smallestDistance = Double.MAX_VALUE;
		double distance;
		Region closestRegion = null;
		for (Region region : regionList) {
			if (region.type == type) {
				distance = GridMap.calculateDistance(coords, region.getCenter());
				if (null == closestRegion || distance < smallestDistance) {
					smallestDistance = distance;
					closestRegion = region;
				}
			}
		}
		return closestRegion;
	}
	
	
	
	public LinkedList<Coordinates> findPath(Coordinates start, Coordinates goal) {
		aStarPathFinder as = new aStarPathFinder(start, goal, -1);
		return as.execute();
	}
	
	public LinkedList<Coordinates> findPath(Coordinates start, Coordinates goal, int depthConstraint) {
		aStarPathFinder as = new aStarPathFinder(start, goal, depthConstraint);
		return as.execute();
	}
	
	/* ***********************************************************************
	 * ***********************************************************************
	 * 
	 * 	A* Stuff
	 * 
	 * ***********************************************************************
	 * ***********************************************************************
	 */
	
	class Node implements Comparable<Node> {
		final Coordinates coords;
		Node parent;
		double f;
		int g;
		
		Node(Coordinates coords, Node parent, int g) {
			this.coords = coords;
			this.parent = parent;
			this.g = g;
		}

		public int compareTo(Node o) {
			if (this.f < o.f) return -1;
			if (this.f == o.f) return 0;
			return 1;
		}
		
		public boolean equals(Object o) {
			if (this == o) return true;
			if (!(o instanceof Node)) return false;
			Node n = (Node) o;
			if (this.coords.equals(n.coords)) return true;
			return false;
		}
		
		public int hashCode() {
			int hash = 17;
			hash = 31 * hash + coords.x;
			hash = 31 * hash + coords.y;
			return hash;
		}
	}

	class aStarPathFinder {
		PriorityQueue<Node> open;
		HashMap<Node,Node> closed;
		Coordinates goal;
		Node best;
		int depthConstraint;
		
		aStarPathFinder(Coordinates start, Coordinates goal, int depthConstraint) {
			this.goal = goal;
			this.depthConstraint = depthConstraint;
			open = new PriorityQueue<Node>();
			closed = new HashMap<Node,Node>();
			best = new Node(start, null, 0);
			open.add(best);
		}
		
		public LinkedList<Coordinates> execute() {
			Node current;
			best.f = h(best);
			
			while ((current = open.poll()) != null) {
				if (current.coords.equals(goal)) return getPath(current);	
				closed.put(current, current);
				
				//Constrain search
				if (current.f-current.g < best.f-best.g) best = current;
				if (depthConstraint > 0 && current.g >= depthConstraint) continue;
				
				NeighborProvider np = new NeighborProvider(current.coords, goal);
				Coordinates c;
				while ((c = np.next()) != null){
					int cost = current.g + 1;
					Node neighbor = new Node(c, current, cost);
					Node neighbor2;
					if (open.contains(neighbor)) {
						if (neighbor.g < (neighbor2 = getNode(open, neighbor)).g) {
							open.remove(neighbor2);
							neighbor.f = neighbor.g + h(neighbor);
							open.add(neighbor);
						}
						// it's in open, and this one is not better, do nothing.
					} else if (closed.containsKey(neighbor)) {
						if (neighbor.g < (neighbor2 = closed.get(neighbor)).g) {
							closed.remove(neighbor2);
							neighbor.f = neighbor.g + h(neighbor);
							open.add(neighbor);
						}
						// it's in closed and this one is not better, do nothing.
					} else {
						// It was in neither, add it.
						neighbor.f = neighbor.g + h(neighbor);
						open.add(neighbor);
					}
				}
			}
			
			return best == null ? null : getPath(best);
		}
		
		private LinkedList<Coordinates> getPath(Node node) {
			LinkedList<Coordinates> path = new LinkedList<Coordinates>();
			Node n = node;
			do {
				path.addFirst(n.coords);
			} while ((n = n.parent) != null);  
			return path;
		}

		private Node getNode(Iterable<Node> list, Node node) {
			Iterator<Node> it = list.iterator();
			Node n;
			while (!(n = it.next()).equals(node));
			return n;
		}

		private double h(Node n) {
			return GridMap.calculateDistance(n.coords, goal);
		}
		
		private int g(Node n) {
			return n.g;
		}
		
	}
	
	class NeighborProvider {
		Coordinates coords, goal;
		private int counter;
				
		NeighborProvider(Coordinates coords, Coordinates goal) {
			this.counter = 0;
			this.coords = coords;
			this.goal = goal;
		}
		
		public Coordinates next() {
			if (counter == neighborProviderRelativeCoords.length) return null;
			Coordinates c = new Coordinates(
					coords.x + neighborProviderRelativeCoords[counter++], 
					coords.y + neighborProviderRelativeCoords[counter++] 
			); 
			if (isFree(c) || c.equals(goal)) return c;
			return next();
		}
	}

	public LinkedList<Region> getRegionsAt(Coordinates c) {return getRegionsAt(c.x, c.y);}
	public LinkedList<Region> getRegionsAt(int x, int y) {
		LinkedList<Region> regions = new LinkedList<Region>();
		for (Region r : regionList) {
			if (r.contains(x, y)) regions.add(r);
		}
		return regions;
	}
	public LinkedList<Region> getSpecificRegionsAt(Coordinates c, RegionType type) {return getSpecificRegionsAt(c.x, c.y, type);}
	public LinkedList<Region> getSpecificRegionsAt(int x, int y, RegionType type) {
		LinkedList<Region> regions = new LinkedList<Region>();
		for (Region r : regionList) {
			if (r.type == type && r.contains(x, y)) regions.add(r);
		}
		return regions;
	}
	public boolean isInRegion(Coordinates c, RegionType type) {return isInRegion(c.x, c.y, type);}
	public boolean isInRegion(int x, int y, RegionType type) {
		return getSpecificRegionsAt(x, y, type).size() > 0;
	}
}
